/*
 * cube.h
 *
 *  Created on: Sep 19, 2013
 * @author Daniel Rogers
 *
 */

#ifndef CUBE_H_
#define CUBE_H_

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#include "utils.h"

/* ======================================================================== */
/*                           DEFINES AND STRUCTS                            */
/* ======================================================================== */

//Cubie locations, as initials
//  in order (C)orner or (E)dge
//  (T)op or (M)iddle or (B)ottom
//  (R)ight or (B)ack or (L)eft or (F)ront
#define C_TBR 0
#define C_TBL 1
#define C_TFL 2
#define C_TFR 3
#define C_BBR 4
#define C_BBL 5
#define C_BFL 6
#define C_BFR 7

#define E_TB 0
#define E_TL 1
#define E_TF 2
#define E_TR 3
#define E_MBR 4
#define E_MBL 5
#define E_MFL 6
#define E_MFR 7
#define E_BB 8
#define E_BL 9
#define E_BF 10
#define E_BR 11

#define FACE_TURNS_MAX 20
#define Q_TURNS_MAX 29

typedef struct Cube
{
    //encoded corner Cubie state
    uint16_t corners;
    //Orientation of corner cubies
    uint16_t corner_spin;

    //packed edge cubie state
    uint8_t edges[6];
    //orientation of edge cubies
    uint16_t edge_spin;

} Cube;

//The minimum number of bits needed to store a cube
//  - technically you could shave 1 more bit off, but it's not worth it
//This saves space over storing two 32-bit values and a 16-bit value because
//  this will use 69 bytes for 8 values instead of  80 bytes
//Has a storage savings of ~ 27% over normal (69 bytes vs 96 bytes)
//This slower than using normal cubes, but during table generation
//  this can save multiple GB in terms of storage space
#define CUBES_PER_SET 8
typedef struct
{
    /*
     * 8 cubes compressed together into 69 bytes
     * vs 96 for a normal set
     */
    uint8_t data[69];
} CompressedCubeSet;

//Counter-clockwise from top-back
//  0001 0000 -> 0x10
//  0011 0010 -> 0x32
//  0101 0100 -> 0x54
//  0111 0110 -> 0x76
//  1001 1000 -> 0x98
//  1011 1010 -> 0xBA

static const Cube UNIT_CUBE =
{ 0, 0,
{ 0x10, 0x32, 0x54, 0x76, 0x98, 0xBA }, 0 };

/* ======================================================================== */
/*                          PUBLIC INTERFACE                                */
/* ======================================================================== */

/*
 * Converts an uncompressed cube to a compressed cube
 * @param src The source cube to compress
 * @param which member (0-7) to write to
 * @param dest The Compressed cube to write to
 */
void compressCube(Cube * const src, CompressedCubeSet * dest, uint8_t to);

/*
 * Converts a compressed cube to an uncompressed cube
 * @param src The source Compressed cube to decompress
 * @param from which member to read from
 * @param dest The cube to write to
 */
void decompressCube(CompressedCubeSet * const src, uint8_t from, Cube * dest);

/*
 * Gets a cube with all faces set to solved values
 *
 * @param cube The cube state to store the unit cube in
 */
void getUnitCube(Cube * cube);

/*
 * Rotate the top face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateTop(const Cube cube);

/*
 * Rotate the bottom face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateBottom(const Cube cube);

/*
 * Rotate the left face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateLeft(const Cube cube);

/*
 * Rotate the right face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateRight(const Cube cube);

/*
 * Rotate the front face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateFront(const Cube cube);

/*
 * Rotate the back face of the cube by 1/4 turn counter-clockwise
 *
 * @param cube The Cube to perform the operation on.
 * @return A Cube with that has been rotated.
 */
Cube rotateBack(const Cube cube);

/*
 * This generates all single-turn permutation of a cube state
 *
 * @param initial The Cube state to permute
 * @param[out] permutations An array to store the permuted cube states in
 *              The order will be top, bottom, left, right, front, back
 */
void permuteAll(const Cube initial, Cube permutations[6]);

/*
 * This generates all face-turn permutation of a cube state
 *
 * @param initial The Cube state to permute
 * @param[out] permutations An array to store the permuted cube states in
 *              The order will be top, bottom, left, right, front, back in sets
 *                  of 1/4, 1/2, and 3/4 turns
 */
void permuteAllFaces(const Cube initial, Cube permutations[18]);

/*
 * Checks if two cubes are equal
 *
 * @param cube1 The first Cube to check with
 * @param cube2 The second Cube to check with
 *
 * @return 0 if they are not equal
 */
bool equalCubes(const Cube * const cube1, const Cube * const cube2);

/*
 * Displays a cube state
 */
void printCube(const Cube cube);

/*
 * Returns the heuristic table values for a cube state
 *
 * @param htables The heuristic tables to use
 * @param cube The cube state to look up
 * @param distances[out] An array of uint8_t[3] to store the heuristics in in
 *                       the order corner, edge1, edge2
 */
void getCubeHeuristics(uint8_t * const htables[3], const Cube cube,
        uint8_t distances[3]);

/*
 * Reads the values from the heuristic tables
 *
 * @param htables An array of pointers to the tables to look up the values in
 *                  in the order corner, edge1, edge2 table
 * @param indexes An array of 3 unit32_t indexes to access from the table
 * @param[out] distances The distances stored in the tables in a uint8_t[3]
 */
void getHeuristics(uint8_t * const htables[3], const uint32_t indexes[3],
        uint8_t distances[3]);

/*
 * Gets the array indexes for the corners and two edge sets
 *
 * @param cube The cube to get the indexes for
 * @param indexes[out] An array that will contain the corner, edge1, and edge2
 *                      indexes
 */
void getCodedIndexes(const Cube * const cube, uint32_t indexes[3]);

/*
 * Calculates the encoded value for a corner cubie from the set of faces
 *
 * @param faces An array of 3 characters in the set {R, O, Y, G, B, W}
 *              Expects in the order [top/bot, front/back, left/right]
 * @param corners An array to store the calculated corner value in
 * @param cparity An array to store the calculated parity value in
 * @param spinstr A pointer to the bit string containing the spin values
 * @param pos The position of the cubie being evaluated
 *
 * @return True if it was a valid corner cubie. False if not
 */
bool evaluateCorner(char faces[3], uint8_t corners[8], uint8_t cparity[8],
        uint16_t * spinstr, uint8_t pos);

/*
 * Calculates the encoded value for an edge cubie from the set of faces
 *
 * @param faces An array of 2 characters in the set {R, O, Y, G, B, W}
 *              Expects in the order: [top/bot, other] or
 *              if first not possible: [front/back, other]
 * @param edges An array to store the calculated edge value in
 * @param eparity An array to store the calculated parity value in
 * @param spinstr A pointer to the bit string containing the spin values
 * @param pos The position of the cubie being evaluated
 *
 * @return True if it was a valid corner cubie. False if not
 */
bool evaluateEdge(char faces[2], uint8_t edges[12], uint8_t eparity[12],
        uint16_t * spinstr, uint8_t pos);

/*
 * Outputs a cube state to stdout
 *
 * @param cube The cube to print
 */
void printCube(Cube const cube);

/* ======================================================================== */
/*                      PRIVATE UTILITY METHODS                             */
/* ======================================================================== */

/*
 * Converts from the unpacked representation of the corner cubies to a packed
 * representation
 *
 * @param[in] corners An array of uint8_t[8] containing the corner cubie state
 *
 * @param[out] out A uint16_t* to store the encoded bit string in
 */
void encodeCorners(const uint8_t corners[8], uint16_t * out);

/*
 * Converts from the packed representation of the corner cubies to an unpacked
 * representation
 *
 * @param[in] cornerStr The bit string representing the state of the corner
 *                      cubies
 * @param[out] out An array of uint8_t[8] to store the decoded values in in
 *              the order: top-back-right, top-back-left,
 *                         top-front-left, top-front-right,
 *                         bot-back-right, bot-back-left,
 *                         bot-front-left, bot-front-right
 */
void decodeCorners(const uint16_t cornerStr, uint8_t out[8]);

/*
 * Converts from the unpacked representation of the edge cubies to a packed
 * representation
 *
 * @param[in] edges An array of uint8_t[12] containing the corner cubie state
 *
 * @param[out] out A uint32_t[2] to store the encoded bit strings in
 */
void encodeEdges(const uint8_t edges[6], uint32_t out[2]);

/*
 * Encodes all of the edges to a single bit field
 */
void encodeAllEdges(uint8_t edges[12], uint32_t * out);

/*
 * Converts from the packed representation of the edge cubies to an unpacked
 * representation
 *
 * @param[in] edgeStr The bit string representing the state of the edge cubies
 *
 * @param[out] out An array of uint8_t[12] to store the decoded values in in
 *              the order: top back, left, front, right,
 *                         mid back-right, back-left, front-left, front-right,
 *                         bot back, left, front, right,
 */
void decodeEdges(uint32_t edgeStr, uint8_t out[12]);

/*
 * Converts from an expanded representation back to the bit-packed representation
 *
 * @param[in] edges The uncompressed edge state
 * @param[out] out The compressed edge state
 *
 */
void compressEdges(const uint8_t edges[12], uint8_t out[6]);

/*
 * Converts from the bit-packed representation of the edge states to the
 * unpacked representation
 *
 * @param[in] packed The compressed edge state
 *
 * @param[out] out An array of uint8_t[12] to store the decoded values in in
 *              the order: top back, left, front, right,
 *                         mid back-right, back-left, front-left, front-right,
 *                         bot back, left, front, right,
 */
void decompressEdges(const uint8_t packed[6], uint8_t out[12]);

/*
 * Calculates the offset of a value for encoding
 *
 * @param values An array of uint8_t to use to calculate the offset
 * @param val The index of the value to compute the offset of
 *
 * @return A uint8_t representing the offset for the value
 */
uint8_t calcOffset(const uint8_t * const values, uint8_t val);

/*
 * Determines the offset and actual value of a decoded corner value
 *
 * @param choices The possible values the decoded value could be
 * @param known The current list of decoded values
 * @param fakeval The raw decoded value that needs to be converted
 * @param len The number of known values
 *
 * @return The value of fakeval prior to when when it was offset during
 *          encoding
 */
uint8_t findRealCorner(const uint8_t choices[8], const uint8_t known[8],
        uint8_t fakeval, uint8_t len);

/*
 * Determines the offset and actual value of a decoded edge value
 */
uint8_t findRealEdge(const uint8_t choices[12], const uint8_t known[12],
        uint8_t fakeval, uint8_t len);

/*
 * Gets the smallest value in an array
 */
uint8_t getMin(const uint8_t * const values, uint8_t len);

/*
 * Computes the spin of a cubie
 *
 * @param cubie The cubie to compute the spin of
 * @param spin The current spin of the cubie
 * @param corner If it's a corner cubie
 * @param op The operation performed on it
 *              Top - 0, Bot - 1,
 *              Left - 2, Right - 3,
 *              Front - 4, Back - 5
 * @param pos The START position of the cubie
 *
 * @return The value representing the spin of the cubie
 */
uint8_t calcSpin(uint8_t cubie, uint8_t spin, bool corner, uint8_t op,
        uint8_t pos);

/*
 * Convenience function for updating spin indexes
 *
 * @param str A pointer to a bit string holding the current spin state
 *              This will be ALTERED and updated with the new spin state
 * @param cubie The id of cubie
 * @param startPos The start position of the cubie
 * @param op The operation being performed
 *              0/1 - top/bot rotation
 *              2/3 - left/right rotation
 *              4/5 - front/back rotation
 * @param corner true if the cubie is a corner cubie, false if edge
 */
void updateSpin(uint16_t * str, uint8_t cubie, uint8_t startPos, uint8_t op,
bool corner);

/*
 * Convenience function for updating spin indexes
 *
 * @param[out] str A pointer to the spin string to be modified
 * @param spin The new spin value
 * @param cubie The cubie being updated
 * @param corner If the cubie is a corner or an edge cubie
 */
void insertSpin(uint16_t * str, uint8_t spin, uint8_t cubie, bool corner);

/*
 *  * Convenience function for updating spin indexes
 *
 * @param str A 16bit string to extract from
 * @param cubie The cubie being extracted
 * @param corner If the cubie is a corner or an edge cubie
 */
uint8_t extractSpin(uint16_t * str, uint8_t cubie, bool corner);

/*
 * Swaps 4 cubies
 *
 * @param cubies The cubie array to swap in
 * @param str The spin state string to update
 * @param p1 through p4 The positions to rotate through
 *          afterwards, p1=p2, p2=p3, p3=p4, p4=p1
 * @param op The rotation being performed as 0,1,2,3,4,5
 * @param corner If the operation is on corner or edge cubies
 */
void swapCubies(uint8_t * cubies, uint16_t * str, uint8_t p1, uint8_t p2,
        uint8_t p3, uint8_t p4, uint8_t op, bool corner);

#endif /* CUBE_H_ */
